#include <stdio.h>
#include <stdlib.h>

int pages[1000001], time[1000001];
int main()
{
    int size, r = 0;
    printf("Please input the working set size: ");
    scanf("%d", &size);
    for (int now_time = 0;;++now_time)
    {
        int pgnum, i;
        printf("Please input the virtual page number: ");
        scanf("%d", &pgnum);

        #ifdef debug
        if (pgnum == -1)
        {
            for (i = 0; i < r; ++i)
                printf("%d %d\n", pages[i], time[i]);
            continue;
        }
        #endif

        for (i = 0; i < r; ++i)
            if (now_time - time[i] >= size && time[i] != -1)
            {
                if (pages[i] != pgnum)
                {
                    time[i] = -1;
                    printf("Page number #%d is taken out.\n", pages[i]);
                }
                break;
            }
        for (i = 0; i < r; ++i)
            if (pages[i] == pgnum && time[i] != -1)
            {
                time[i] = now_time;
                printf("The page has already in the memory.\n");
                break;
            }
        if (i >= r)
        {
            for (i = 0; i < r; ++i)
                if (time[i] == -1)
                {
                    time[i] = now_time;
                    pages[i] = pgnum;
                    break;
                }
            if (i >= r)
            {
                time[r] = now_time;
                pages[r++] = pgnum;
            }
            printf("Missed. The page has been moved into memory.\n");
        }
    }
}
